#define _CRT_SECURE_NO_WARNINGS 1
/*
		轮转数组
*/

void reverse(int* nums, int left, int right)
{
    while (left <= right)
    {
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
        left++;
        right--;
    }
}
void rotate(int* nums, int numsSize, int k)
{
    k %= numsSize;
    reverse(nums, 0, numsSize - k - 1);
    reverse(nums, numsSize - k, numsSize - 1);
    reverse(nums, 0, numsSize - 1);
}


/*
    消失的数字
*/

//法一：先求出0~n的数之和，最后遍历减去数组元素，剩下的就是消失的数字
int missingNumber(int* nums, int numsSize)
{
    int sum = (0 + numsSize) * (numsSize + 1) / 2;
    int i = 0;
    for (i = 0; i < numsSize; i++)
    {
        sum -= nums[i];
    }
    return sum;
}

//法二：

int missingNumber(int* nums, int numsSize)
{
    int ret = 0;
    int i = 0;
    for (i = 0; i <= numsSize; i++)
    {
        ret ^= i;
    }
    for (i = 0; i < numsSize; i++)
    {
        ret ^= nums[i];
    }
    return ret;
}


/*
    两数之和
*/

int compar(const void* p1, const void* p2)
{
    return *((int*)p1) - *((int*)p2);
}

int* twoSum(int* nums, int numsSize, int target, int* returnSize)
{
    //返回数组
    int* ret = (int*)malloc(sizeof(int) * 2);
    *returnSize = 2;

    //将该数组复制一份
    int* numscopy = (int*)malloc(sizeof(int) * numsSize);
    int i = 0;
    for (i = 0; i < numsSize; i++)
    {
        numscopy[i] = nums[i];
    }

    //先排序原数组
    qsort(nums, numsSize, sizeof(int), compar);

    //找到满足条件的两个数
    int left = 0;
    int right = numsSize - 1;
    while (left <= right)
    {
        int sum = nums[left] + nums[right];
        if (sum < target)
        {
            left++;
        }
        else if (sum > target)
        {
            right--;
        }
        else
        {
            break;
        }
    }

    //在遍历原数组找到相同元素的对应下表
    for (i = 0; i < numsSize; i++)
    {
        if (numscopy[i] == nums[right])
        {
            ret[0] = i;
        }
    }
    for (i = 0; i < numsSize; i++)
    {
        if (numscopy[i] == nums[left] && i != ret[0])
        {
            ret[1] = i;
        }
    }
    // int a1 = 0;
    // int a2 = numsSize-1;
    // while(a1<=numsSize)
    // {
    //     if(numscopy[a1] == nums[left])
    //     {
    //         ret[0] = a1;
    //     }
    //     else if(numscopy[i] == nums[left])
    //     {
    //         ret[1] = a2;
    //     }
    //     a1++;
    //     a2--;
    // }
    return ret;
}